/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-03-19
 * Time: 22:01
 */
public class Sort {
    /*
    直接插入排序
    时间复杂度：O(N^2)
    空间复杂度：O(1)
    稳定性：稳定
     */
    public static void insertSort(int[] array){
        //直接插入排序
        for(int i=1;i<array.length;i++){
            int j=i-1;
            int key=array[i];
            while(j>=0){
                if(array[j]>key){
                    array[j+1]=array[j];
                    j--;
                    //升序
                }else{
                    array[j+1]=key;
                    break;
                }
            }
            array[j+1]=key;
        }
    }


    /*
    希尔排序
    时间复杂度：O(N^1.3)
    空间复杂度：O(1)
    稳定性：不稳定
     */
    public static void shellSort(int[] array){
        //希尔排序
        //分组排序
        int gap=array.length/2;

        while(gap>=1){
            for(int i=gap;i<array.length;i++){
                int key=array[i];
                int j=i-gap;
                while(j>=0){
                    if(array[j]>key){
                        array[j+gap]=array[j];
                        j-=gap;
                    }else{
                        break;
                    }
                }
                array[j+gap]=key;
            }
            gap=gap/2;
        }
    }


    /*
    选择排序
    时间复杂度：O(N^2)
    空间复杂度：O(1)
    稳定性：不稳定
     */
    public static void selectSort(int[] array){
        //选择排序
        //找最小值
        int left=0;
        while(left<array.length){
            int minnum=left;
            for(int j=left+1;j<array.length;j++){
                if(array[j]<array[minnum]){
                    minnum=j;
                }
            }
            swap(array,left,minnum);
            left++;
        }
    }

    public static void selectSort2(int[] array){
        //选择排序
        //找最大值和最小值
        int left=0;
        int right=array.length-1;
        while(left<right){
            int minnum=left;
            int maxnum=left;
            for(int i=left;i<=right;i++){
                if(array[minnum]>array[i]){
                    minnum=i;
                }
                if(array[maxnum]<array[i]){
                    maxnum=i;
                }
            }
            swap(array,minnum,left);
            if(maxnum==left){
                maxnum=minnum;
            }
            swap(array,maxnum,right);
            right--;
            left++;
        }
    }


    //交换函数
    public static void swap(int[] array,int i,int j){
        int ret=array[i];
        array[i]=array[j];
        array[j]=ret;
    }


    /*
    堆排序
    时间复杂度：O(N*logN)
    空间复杂度：O(1)
    稳定性：稳定
     */
    public static void heapSort(int[] array){
        //堆排序
        //先建堆，然后使用向下调整来排序
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            abjustDown(array,0,end);
            end--;
        }
    }
    //建一个大堆,排升序
    public static void createHeap(int[] array){
        //从第一个非叶子结点开始
        for(int i=(array.length-1-1)/2;i>=0;i--){
            abjustDown(array,i,array.length);
        }
    }
    //向下调整
    public static void abjustDown(int[] array,int parent,int len){
        int child=parent*2+1;//左孩子
        while(child<len){
            if(child+1<len&&array[child+1]>array[child]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }



    //递归和非递归


}
